package skipList

import (
	"fmt"
	"math/rand"
)
const MaxLevel = 32
const SkipP = 2
type SkipList struct{
	head *Node
	len int
	level int
}

type Node struct{
	forward []*Node
	key int
	value interface{}
}

func InitializeSkipList() *SkipList{
	return &SkipList{
		head: &Node{
			forward:make([]*Node, 1, 1),
		},
		level: 1,
		len: 0,
	}
}

func (sk *SkipList)Insert(key int) {
	level := sk.randomLevel()
	newNode := &Node{
		key:key,
		forward: make([]*Node, level, level),
	}
	if level > sk.level {
		for i := sk.level; i < level; i++ {
			sk.head.forward = append(sk.head.forward, newNode)
		}
		fmt.Println("level: ", level, sk.head.forward)
	}
	update := make(map[int]*Node)
	for i,node:=sk.level-1,sk.head; i>=0; i--{
		if i == 1 {
			fmt.Println(node.forward)
		}
		for ;node.forward[i] != nil && node.forward[i].key < key; node = node.forward[i]{}
		if node.forward[i]!= nil && node.forward[i].key == key {
			return
		}
		if level > i {
			update[i] = node
		}
	}
	for k,_ := range update{
		newNode.forward[k] = update[k].forward[k]
		update[k].forward[k] = newNode
	}
	if level > sk.level{
		sk.level = level
	}
	sk.len++
}

func (sk *SkipList)Delete(key int){
	update := make([]*Node, sk.level, sk.level)
	for i,node:=sk.level-1,sk.head;i>=0;i-- {
		for ;node.forward != nil && node.forward[i].key < key;node = node.forward[i] {}
		if node.forward[i] != nil && node.forward[i].key == key {
			update[i] = node
		}
	}

	for k, _ := range update {
		if update[k] == nil {
			break
		}
		update[k].forward[k], update[k].forward[k].forward[k] = update[k].forward[k].forward[k], nil
	}
}

func (sk *SkipList)Search(key int) (res *Node){
	for i,node:=sk.level-1,sk.head;i>=0;i--{
		for ;node.forward != nil && node.forward[i].key <= key;node=node.forward[i] {}
		if node.key == key {
			res = node
			break
		}
	}
	return
}

func (sk *SkipList)randomLevel()int{
	level := 1
	for (rand.Int31()&0xFFFF) % SkipP == 0 {
		level ++
	}
	if level < MaxLevel {
		return level
	}else{
		return MaxLevel
	}
}

func (sk *SkipList)PrintAll(){
	for i:=sk.level-1;i>=0;i--{
		for node := sk.head.forward[i]; node != nil; node = node.forward[i]{
			fmt.Printf("%d ", node.key)
			if node.forward[i] == nil{
				break
			}
		}
		fmt.Println()
		fmt.Println(i,"-----------------------------------------")
	}
}
//endregion